package 记忆化搜索;

import java.util.Arrays;

//198 打家劫舍
public class Solution1 {
    public int rob(int[] nums) {
        dp = new int[nums.length];
        Arrays.fill(dp,-1);
        return dfs(0,nums);
    }
    int[] dp;
    int dfs(int index, int[]nums){
        if(index>=nums.length) return 0;
        if(dp[index]!=-1) return dp[index];//记搜，如果不是初始化状态就返回存储的记录，避免大量递归
        return dp[index] = Math.max(dfs(index+1,nums),dfs(index+2,nums)+nums[index]);
    }
}
